By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 38, Issue 5, pp. 1661-2112

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Universal Arguments and their Applications

Boaz Barak and Oded Goldreich

pp. 1661-1694

BibTeX  Abstract Full Text:  PDF

Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf

pp. 1695-1708

BibTeX  Abstract Full Text:  PDF

Graph Distances in the Data-Stream Model

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang

pp. 1709-1727

BibTeX  Abstract Full Text:  PDF

Private Approximation of Search Problems

Amos Beimel, Paz Carmi, Kobbi Nissim, and Enav Weinreb

pp. 1728-1760

BibTeX  Abstract Full Text:  PDF

Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs

Yuval Emek and David Peleg

pp. 1761-1781

BibTeX  Abstract Full Text:  PDF

The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)

Libor Barto, Marcin Kozik, and Todd Niven

pp. 1782-1802

BibTeX  Abstract Full Text:  PDF

Spanners of Complete $k$-Partite Geometric Graphs

Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, and Michiel Smid

pp. 1803-1820

BibTeX  Abstract Full Text:  PDF

Profiles of Tries

Gahyun Park, Hsien-Kuei Hwang, Pierre Nicodème, and Wojciech Szpankowski

pp. 1821-1880

BibTeX  Abstract Full Text:  PDF

On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs

Umberto Straccia, Manuel Ojeda-Aciego, and Carlos V. Damásio

pp. 1881-1911

BibTeX  Abstract Full Text:  PDF

Impossibility Results and Lower Bounds for Consensus under Link Failures

Ulrich Schmid, Bettina Weiss, and Idit Keidar

pp. 1912-1951

BibTeX  Abstract Full Text:  PDF

Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers

Kiran S. Kedlaya and Sergey Yekhanin

pp. 1952-1969

BibTeX  Abstract Full Text:  PDF

The Complexity of Weighted Boolean CSP

Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum

pp. 1970-1986

BibTeX  Abstract Full Text:  PDF

On the Complexity of Numerical Analysis

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen

pp. 1987-2006

BibTeX  Abstract Full Text:  PDF

Interval Completion Is Fixed Parameter Tractable

Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle

pp. 2007-2020

BibTeX  Abstract Full Text:  PDF

Optimizing Schema Languages for XML: Numerical Constraints and Interleaving

Wouter Gelade, Wim Martens, and Frank Neven

pp. 2021-2043

BibTeX  Abstract Full Text:  PDF

Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams

Sudipto Guha and Andrew McGregor

pp. 2044-2059

BibTeX  Abstract Full Text:  PDF

Sampling Algorithms and Coresets for $\ell_p$ Regression

Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney

pp. 2060-2078

BibTeX  Abstract Full Text:  PDF

Hierarchical Unambiguity

Holger Spakowski and Rahul Tripathi

pp. 2079-2112

BibTeX  Abstract Full Text:  PDF